import java.util.*;
public class Tree_Linked {
    //牛克 JZ36 二叉搜索树与双向链表
     public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
        public static TreeNode first;
        public static TreeNode last;
        public TreeNode Convert(TreeNode pRootOfTree) {
            TreeNode  root=pRootOfTree;
            zhongxun(root);
            return first;
        }
        public static void zhongxun(TreeNode root){
            if(root==null){
                return;
            }
            zhongxun(root.left);
            //构建双向链表
            wshuangl(root);
            zhongxun(root.right);
        }
        public static int j=0;
        public static void wshuangl(TreeNode cur){
            if(j==0){
                first=cur;
                last=cur;
                j++;
            }else{
                last.right=cur;
                cur.left=last;
                last=cur;
            }
        }
    }


